package 剑指Offer;

public class Offer60_n个骰子的点数 {
    public double[] dicesProbability(int n) {
        if (n <= 0) {
            return new double[0];
        }
        /*
        首先为了方便表达（dp[0][0]是没有含义的），我们将 dp 数组的行的数量设为 n + 1，列的数量设为 6n + 1。
        行表示 n，列表示 s，且 s 的最大值是 6n。
         */
        //dp[n][s] 表示投掷 n 个骰子，n 个朝上的面的点数之和为 s 的事件出现的次数
        int[][] dp = new int[n + 1][6 * n + 1];

        /*
            初始化 一颗骰子的情况.
            一颗骰子， s 的每个值可能出现的次数都为 1
        */
        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {//表示骰子的个数
            for (int s = i; s <= 6 * i; s++) {//表示可能会出现的点数之和
                for (int j = 1; j <= 6; j++) {//表示当前这个骰子可能掷出的点数
                    if (s - j > 0) {//没有骰子能投掷出小于等于 0 的点数
                        dp[i][s] += dp[i - 1][s - j];//当前n个骰子出现的点数之和等于n-1个骰子出现的点数之和加上这一个出现的点数
                    } else {
                        break;
                    }
                }
            }
        }
        double total = Math.pow((double) 6, (double) n);//有多少种点数配对情况，比如两骰子有6²=36种配对情况，也即骰子出现的和的次数为36次
        double[] ans = new double[5 * n + 1];//n个骰子「点数和」的范围为 [n, 6n] ，数量为 6n - n + 1 = 5n + 1 种。
        for (int i = n; i <= 6 * n; i++) {
            ans[i - n] = ((double) dp[n][i]) / total;//第i小的点数出现的概率
        }
        return ans;
    }
}
